package interview.shiftedbinarysearch;

public class ShiftedBinarySearch {
	// Assuming array is sorted in ascending order
	public int binarySearch(int[] array, int target) {
		int left = 0;
		int right = array.length - 1;
		int mid;
		while(left <= right) {
			mid = left + (right - left) / 2;
			if(array[mid] == target) {
				return mid;
			} else if (array[mid] < target) {
				left = mid + 1;
			} else {
				right = mid - 1;
			}
		}
		return -1;
	}

	// Assuming array is sorted in ascending order
	public int shiftedBinarySearch(int[] array, int target) {
		// Array is not shifted, fall back to normal binary search
		if(array[array.length - 1] > array[0]) {
			return binarySearch(array, target);
		}
		int left = 0;
		int right = array.length - 1;
		int mid;
		while(left <= right) {
			mid = left + (right - left) / 2;
			if(array[mid] == target) {
				return mid;
			} else if (array[mid] < target) {
				if(target >= array[0]) {
					right = mid - 1;
				} else {
					left = mid + 1;
				}
			} else {
				if(target < array[0]) {
					left = mid + 1;
				} else {
					right = mid - 1;
				}
			}
		}
		return -1;
	}
}
